<?php

class TreeNode
{
    public $val = null;
    public $left = null;
    public $right = null;

    function __construct($val = 0, $left = null, $right = null)
    {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution
{

    /**
     * @param TreeNode $root
     * @return TreeNode
     */
    private $r;

    function increasingBST($root)
    {
        $this->travel($root, new TreeNode(null));
        return $this->r;
    }

    function travel($root, &$newR)
    {
        if ($root) {
            $this->travel($root->left, $newR);
            if ($newR->val === null) {
                $newR->val = $root->val;
                $this->r = $newR;
            } else {
                $newR->right = new TreeNode($root->val);
                $newR->left = null;
                $newR = $newR->right;
            }

            $this->travel($root->right, $newR);
        }
    }
}


?>
